package xyz.xiaotugou.dataStructure.basic;

/**
 * 
 * @Title:  MyLinkedList   
 * @Package xyz.xiaotugou.dataStructure   
 * @Description:  自定义双向链表： 支持新增、删除、查找
 * @author: ysy    
 * @date:   2020年9月1日 上午10:15:27  
 * @version V1.0
 * @param <T>
 */
public class MyLinkedList<T> {
	//头节点指针
    private Node<T> head;
    //尾节点指针
    private Node<T> tail;
    //链表实际长度
    private int size;
    
	/**
     * 链表节点
     */
    public static class Node<T> {
        T data;
        Node<T> next;
        Node<T> prev;
        Node(T data) {
            this.data = data;
        }
    }
    
    public void add(T data) throws Exception {
    	add(size, data);
    }
    
    public void add(int index, T data) throws Exception {
    	if (index<0 || index>size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
    	Node<T> insertedNode = new Node<T>(data);
    	if(size == 0){
    		head = insertedNode;
    		tail = insertedNode;
    	}else if(size == index){
    		Node<T> temp = tail;
            tail = insertedNode;
            temp.next = tail;
            tail.prev = temp;
    	}else{
    		//插入中间
    		Node<T> origin = get(index);
            Node<T> prev = origin.prev;
            prev.next = insertedNode;
            insertedNode.prev = prev;
            insertedNode.next = origin;
            origin.prev = insertedNode;
    	}
    	size ++;
    }
    public void set(int index, T data){
    	
    }
    public void delete(int index) throws Exception {
    	
    }
    
    public Node<T> get(int index) throws Exception {
    	
    	
    	return null;
    }
    
    /**
     * 获取值为data的元素在链表中的位置（第一次出现的位置，可能含有多个）
     * @param data
     * @return
     */
    public int indexOf(T data){
        if(isEmpty() || data == null){
            return -1;
        }

        int n = 0;
        Node<T> node = head;
        while (n < size){
            if(data.equals(node.data)){
                return n;
            }
            n++;
        }

        return -1;
    }
    /**
     * 判断是否有值为data的元素
     * @param data
     * @return
     */
    public boolean containValue(T data){
        return indexOf(data) != -1;
    }

    /**
     * 获取链表的大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }
    
    /**
     * 输出链表
     */
    public void output(){
        Node<T> temp = head;
        while (temp!=null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
    
}
